package com.zhangkunhao.month05.day21.sort;

public class SelectionSortRecursion {

    // 递归选择排序函数
    public static void selectionSort(int[] arr, int n) {
        if (n <= 1) {
            return; // 基本情况：如果数组只有一个元素或为空，不需要排序
        }

        // 找到数组中最小的元素的索引，minIndex是动态变化的，

        int minIndex = arr.length - n;
        //这里的判断条件不能是i<n，因为n是递减的，
        // 但是被比较的数的索引是从当前位置到最后一个，最后一个的索引是固定的
        for (int i = minIndex + 1; i < arr.length; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
            }
        }

        // 将找到的最小元素交换到当前子数组的起始位置（动态变化）
        swap(arr, minIndex, arr.length - n);

        // 递归地对剩余的子数组进行选择排序
        selectionSort(arr, n - 1);
    }

    // 辅助函数，用于交换数组中的两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 22, 11};
        int n = arr.length;

        selectionSort(arr, n);

        // 打印排序后的数组
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
